//84. 柱状图中最大的矩形

//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//求在该柱状图中，能够勾勒出来的矩形的最大面积。

//class Solution {
//public:
//    int largestRectangleArea(vector<int>& heights) {
//        int n = heights.size();
//        vector<int> left(n, -1);
//        vector<int> right(n, n);
//        stack<int> st;
//        for (int i = 0; i < n; ++i) {
//            while (!st.empty() && heights[i] <= heights[st.top()]) {
//                right[st.top()] = i;
//                st.pop();
//            }
//            left[i] = st.empty() ? -1 : st.top();
//            st.push(i);
//        }
//        int result = 0;
//        for (int i = 0; i < n; ++i) {
//            result = max(result, (right[i] - left[i] - 1) * heights[i]);
//        }
//        return result;
//    }
//};

//1793. 好子数组的最大分数

//给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
//一个子数组(i, j) 的 分数 定义为 min(nums[i], nums[i + 1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
//请你返回 好 子数组的最大可能 分数 。

//class Solution {
//public:
//    int maximumScore(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<int> left(n, -1);
//        stack<int> st;
//        for (int i = 0; i < n; i++) {
//            while (!st.empty() && nums[i] <= nums[st.top()]) {
//                st.pop();
//            }
//            if (!st.empty()) {
//                left[i] = st.top();
//            }
//            st.push(i);
//        }
//
//        vector<int> right(n, n);
//        st = stack<int>();
//        for (int i = n - 1; i >= 0; i--) {
//            while (!st.empty() && nums[i] <= nums[st.top()]) {
//                st.pop();
//            }
//            if (!st.empty()) {
//                right[i] = st.top();
//            }
//            st.push(i);
//        }
//
//        int ans = 0;
//        for (int i = 0; i < n; i++) {
//            int h = nums[i], l = left[i], r = right[i];
//            if (l < k && k < r) {
//                ans = max(ans, h * (r - l - 1));
//            }
//        }
//        return ans;
//    }
//};

//85. 最大矩形

//给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

//class Solution {
//    // 84. 柱状图中最大的矩形
//    int largestRectangleArea(vector<int>& heights) {
//        stack<int> st;
//        st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
//        int ans = 0;
//        for (int right = 0; right < heights.size(); right++) {
//            int h = heights[right];
//            while (st.size() > 1 && heights[st.top()] >= h) {
//                int i = st.top(); // 矩形的高（的下标）
//                st.pop();
//                int left = st.top(); // 栈顶下面那个数就是 left
//                ans = max(ans, heights[i] * (right - left - 1));
//            }
//            st.push(right);
//        }
//        return ans;
//    }
//
//public:
//    int maximalRectangle(vector<vector<char>>& matrix) {
//        int n = matrix[0].size();
//        vector<int> heights(n + 1);
//        int ans = 0;
//        for (auto& row : matrix) {
//            // 计算底边为 row 的柱子高度
//            for (int j = 0; j < n; j++) {
//                if (row[j] == '0') {
//                    heights[j] = 0;
//                }
//                else {
//                    heights[j]++;
//                }
//            }
//            ans = max(ans, largestRectangleArea(heights));
//        }
//        return ans;
//    }
//};

//221. 最大正方形

//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

//class Solution {
//    // 84. 柱状图中最大的矩形
//    // 改成计算最大正方形的边长
//    int largestSize(vector<int>& heights) {
//        stack<int> st;
//        st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
//        int ans = 0;
//        for (int right = 0; right < heights.size(); right++) {
//            int h = heights[right];
//            while (st.size() > 1 && heights[st.top()] >= h) {
//                int i = st.top(); // 矩形的高（的下标）
//                st.pop();
//                int left = st.top(); // 栈顶下面那个数就是 left
//                ans = max(ans, min(heights[i], right - left - 1));
//            }
//            st.push(right);
//        }
//        return ans;
//    }
//
//public:
//    int maximalSquare(vector<vector<char>>& matrix) {
//        int n = matrix[0].size();
//        vector<int> heights(n + 1);
//        int ans = 0;
//        for (auto& row : matrix) {
//            // 计算底边为 row 的柱子高度
//            for (int j = 0; j < n; j++) {
//                if (row[j] == '0') {
//                    heights[j] = 0;
//                }
//                else {
//                    heights[j]++;
//                }
//            }
//            ans = max(ans, largestSize(heights));
//        }
//        return ans * ans;
//    }
//};

//42. 接雨水

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ans = 0;
//        stack<int> st;
//        for (int i = 0; i < height.size(); i++) {
//            int h = height[i];
//            while (!st.empty() && height[st.top()] <= h) {
//                int bottom_h = height[st.top()];
//                st.pop();
//                if (st.empty()) {
//                    break;
//                }
//                int left = st.top();
//                int dh = min(height[left], height[i]) - bottom_h;
//                ans += dh * (i - left - 1);
//            }
//            st.push(i);
//        }
//        return ans;
//    }
//};

//1504. 统计全 1 子矩形

//给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

//class Solution {
//public:
//    int numSubmat(vector<vector<int>>& mat) {
//        int n = mat[0].size();
//        vector<int> heights(n);
//        int ans = 0;
//
//        for (auto& row : mat) {
//            for (int j = 0; j < n; j++) {
//                if (row[j] == 0) {
//                    heights[j] = 0;
//                }
//                else {
//                    heights[j]++;
//                }
//            }
//
//            stack<tuple<int, int, int>> st; // (j, f, heights[j])
//            st.emplace(-1, 0, -1); // 哨兵，方便处理 left=-1 的情况
//            for (int j = 0; j < n; j++) {
//                int h = heights[j];
//                while (get<2>(st.top()) >= h) {
//                    st.pop();
//                }
//                auto [left, f, _] = st.top();
//                // 计算底边为 row，右边界为 j 的子矩形个数
//                // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
//                // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
//                f += (j - left) * h;
//                ans += f;
//                st.emplace(j, f, h);
//            }
//        }
//
//        return ans;
//    }
//};

//1277. 统计全为 1 的正方形子矩阵

//给你一个 m* n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

//class Solution {
//    int solve(vector<int>& heights) {
//        stack<int> st;
//        st.push(-1); // 哨兵：在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
//        int ans = 0;
//        for (int r = 0; r < heights.size(); r++) {
//            int hr = heights[r];
//            while (st.size() > 1 && heights[st.top()] >= hr) {
//                int h = heights[st.top()]; // 矩形的高
//                st.pop();
//                int l = st.top(); // 栈顶下面那个数就是 l
//                int w = r - l - 1;
//                int upper = min(h, w);
//                int lower = (l < 0 ? hr : max(heights[l], hr)) + 1;
//                if (lower <= upper) {
//                    ans += (w * 2 + 2 - lower - upper) * (upper - lower + 1) / 2;
//                }
//            }
//            st.push(r);
//        }
//        return ans;
//    }
//
//public:
//    int countSquares(vector<vector<int>>& matrix) {
//        int n = matrix[0].size();
//        vector<int> heights(n + 1);
//        int ans = 0;
//        for (auto& row : matrix) {
//            for (int j = 0; j < n; j++) {
//                int x = row[j];
//                if (x == 0) {
//                    heights[j] = 0;
//                }
//                else {
//                    heights[j]++;
//                }
//            }
//            ans += solve(heights);
//        }
//        return ans;
//    }
//};